package com.suanfa.matrix;

import java.util.ArrayList;
import java.util.List;

/**
 * int[][] a 行坐标代表从第i个点出发可以到a[i]列表中的点
 */
public class Routings {
    static List<List<Integer>> res = new ArrayList<>();

    static List<Integer> list = new ArrayList<>();

    static int[][] g;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        g = graph;
        dfs(0, g[0]);
        return res;
    }

    public static void dfs(int k, int[] a){
        list.add(k);

        if(k== g.length-1){//已经遍历完,需要去掉最后一个节点，重新走一条路线
            res.add(new ArrayList<>(list));
            list.remove(list.size()-1);
            return;
        }

        for(int i=0; i< a.length; i++){
            dfs(a[i], g[a[i]]);
        }
        list.remove(list.size()-1);
    }

}


class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int[][] g ;
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        g = graph;
        dfs(0,g[0]);
        return res;
    }
    public void dfs(int k,int[] a){
        list.add(k);
        if(k==g.length-1) {
            res.add(new ArrayList<>(list));//踩大坑，直接res.add(list)不行，只能新new一个才行？
            list.remove(list.size()-1);
            return;
        }
        for(int i = 0;i<a.length;i++){
            dfs(a[i],g[a[i]]);
        }
        list.remove(list.size()-1);
    }
}
